package com.example.algorithm.huawei_rongyao_29;

import java.util.Scanner;

// 统计每个月兔子的总数/兔子数列、斐波那契数列

/**
 * 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
 * 例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
 * 一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
 * 数据范围：输入满足1<=n<=31
 *
 * 输入描述:
 * 输入一个int型整数表示第n个月
 *
 * 输出描述:
 * 输出对应的兔子总数
 *
 * 示例1
 * 输入
 * 3
 *
 * 输出
 * 2
 *
 * 以下下程序实际测试正确
 * */
public class Q28_RabbitCount {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入第n个月: ");
        int n = scanner.nextInt();

        if (n < 1 || n > 31) {
            System.out.println("输入的月份必须在1到31之间");
            return;
        }

        System.out.println("第" + n + "个月的兔子总数为: " + getTotalRabbits(n));
    }

    private static int getTotalRabbits(int n) {
        // 前两项是初始项。从第三项开始才能满足当前项等于前两项的和。前两项都是直接写出，并且它们的值固定都是1.
        if (n == 1 || n == 2) {
            return 1;
        }

        // 过了上面这个if没有被return，那说明n是>=3的
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 1;

        for (int i = 3; i <= n; i++) {
            // dp[i]表示第i个月的兔子的总数。当前项dp[i]，等于前两项dp[i - 1]、dp[i - 2]之和。
            // 最后一轮循环，是dp[n]，而dp[n]就是我们要求的第n个月的兔子总数。
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        // 返回第n个月兔子的总数。
        return dp[n];
    }
}

